// 这个方法比较傻，看了discussion后有更好的方法
class Solution {
public:
    // record the result of subVector starting from index
    vector<int> memo;
    int rob(vector<int>& nums) {
        memo = vector<int>(nums.size(), INT_MIN);
        return robPlan(nums, 0);        
    }
    int robPlan(vector<int>& nums, int i) {
        if(i >= nums.size())
            return 0;
        else if(i == nums.size() - 1)
            return nums[i];
        if (memo[i] == INT_MIN)
            memo[i] = max(nums[i] + robPlan(nums, i + 2), nums[i + 1] + robPlan(nums, i + 3));
        return memo[i];
    }   
};

// 这个方法是正常思路
class Solution {
public:
    int rob(vector<int>& nums) {
        // f(n) = max(f(n-1), f(n-2) + i) 
        int preMax = 0;
        int curMax = 0;
        for(int i = 0; i < nums.size(); i++)
        {
            int temp = curMax;
            curMax = max(preMax + nums[i], curMax);
            preMax = temp;
        }
        return curMax;
    }       
};
